package Leetcode.数组字符串;

import java.util.Arrays;

/**
 * @Author kirito
 * @Date 2023/10/31 11:21
 * @PackageName:Leetcode.数组字符串
 * @ClassName: kmp
 * @Description:
 * @Version 1.0
 */
public class KMPAlgorithm {
    public static int kmpSearch(String text, String pattern) {
        int[] next = calculateLPS(pattern);
        System.out.println(Arrays.toString(next));
        int i = 0; // text中的索引
        int j = 0; // pattern中的索引

        while (i < text.length()) {
            if (text.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
                if (j == pattern.length()) {
                    // 匹配成功，返回起始索引
                    return i - j;
                }
            } else {
                if (j != 0) {
                    // 更新pattern中的索引
                    j = next[j - 1];
                } else {
                    i++;
                }
            }
        }
        // 匹配失败，返回-1
        return -1;
    }

    private static int[] calculateLPS(String pattern) {
        int[] lps = new int[pattern.length()];
        int len = 0; // 前缀匹配的长度
        int i = 1;

        while (i < pattern.length()) {
            if (pattern.charAt(i) == pattern.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            } else {
                /*判断前缀起始点是否为0
                * 不为0则起始点=前面那个点的匹配值*/
                if (len != 0) {
                    len = lps[len - 1];
                    /*为0  则起始点没有后缀匹配，当前后缀值为0，后缀++*/
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }

    public static int[] getNext(String pattern) {
        int len = pattern.length();
        int[] next = new int[len];
//        next[0] = 0; // 初始化
//        next[1] = 1;
//        // 从1开始计算next数组
//        for (int i = 2; i < len; i++) {
//            int count = 0;
//            boolean flag = false;
//            for (int j = i-2; j >=0 ; j--) {
//                count++;
//                if (pattern.charAt(i - count) != pattern.charAt(j)) {
//                    break;
//                }else{
//                    flag = true;
//                }
//
//            }
//            if(!flag){
//                next[i] = 1;
//            }
//        }

        return next;
    }



    public static void main(String[] args) {
        String test = "aaaab";
        System.out.println(Arrays.toString(calculateLPS(test)));

//        String text = "ABABDABACDABABCABAB";
//        String pattern = "ABABCABAB";
//        int index = kmpSearch(text, pattern);
//        if (index != -1) {
//            System.out.println("Pattern found at index " + index);
//        } else {
//            System.out.println("Pattern not found");
//        }
    }
}
